Andreas Kirsch
Aufgabe 1: "Nrrische Wirtschaft"

1. Lsungsidee
==============

Ich mchte mit dem wichtigsten und allgemeinsten zuerst anfangen:
Der Kauf bzw. Verkauf von Gegenstnden kostet nichts, deshalb ist die jeweilige Zusammensetzung des Gegenstnde, die der Verein besitzt, nicht relevant fr die Zusammensetzung des Inventars im nchsten Monat, da Verein beliebig Gegenstnde umtauschen kann. Wichtig ist einzig und allein, der Gesamtwert der Gegenstnde, die der Verein besitzt.
Daraus folgt, dass man zur Bestimmung der Gegenstnde, die der Schatzmeister von einen Monat auf den anderen kaufen oder verkaufen soll, nur aus der Gesamtmenge an Gegenstnden die Teilmenge bestimmen muss, die am nchsten an den Wert der Gegenstnde + Budget herankommt, also am wenigsten vom Monatsbudget verschwendet.

Dies ist schon ein wichtiger Schritt zur Lsung, da er das Problem sehr vereinfacht. Jetzt muss man nur noch das grte Teilmenge bestimmen, deren Gesamtwert den alten Gesamtwert + Budget nicht berschreitet.

Die einfachste Strategie ist es, alle Teilmengen zu bestimmen und sie nach ihrem Gesamtwert zu sortieren. Dies wrde fr das Aufgabenbeispiel ausgezeichnet funktionieren, aber bei den Beispielen im Internet gbe es sehr groe Probleme. Eines der Beispiele enthlt 1000 Gegenstnde, die Anzahl der Teilmengen betrgt dann 2^1000, eine Zahl, die man sich nur schwer vorstellen kann und die es keines Falles erlauben wrde, den Akquisitionsplan in ausreichender Zeit zu bestimmen.

Ich benutze aus Mangel an besseren Algorithmen, einen sehr einfachen Ansatz, der aber zumindest bei 4 der 5 Beispiele (Beispiel 0, 1, 3 und 4) optimale Lsungen liefert, da immer das Restgeld = 0 ist (der letzte Datensatz ist dabei egal) und bei dem anderen Beispiele ist das nicht so offensichtlich und konnte daher von mir nicht einfach berprft werden:
Ich verkaufe sozusagen alle Gegenstnde und habe dadurch den Gesamtpreis + Budget Geld zu verfgung.
Die Gesamtliste der Gegenstnde wird dann nach dem Preis absteigend sortiert und ich versuche so viele, teure Gegenstnde wie mglich zu kaufen, bis das Geld verbraucht ist, bzw. alle Gegenstnde einen hheren Preis als das Restgeld haben.
Aus einem Vergleich der alten Liste mit der neuen Liste der Gegenstnde, kann man feststellen, welche Gegenstnde gekauft und welche verkauft worden sind:
alte Liste \ neue Liste ("ohne"): verkaufte Gegenstnde
neue Liste \ alte Liste: gekaufte Gegenstnde

Der Algorithmus ist dann beendet (bzw muss beendet werden, damit keine Endlosschleife anfngt), wenn keine neuen Gegenstnde mehr gekauft werden, also das monatliche Budget nicht angeschnitten wird, also Restgeld >= Budget ist.

Die nchste Frage, die sich stellt, ist: Findet der Algorithmus immer eine Lsung, wenn auch der oben beschriebene Brute-Force-Ansatz eine liefern wrde?
Kurzer Beweis:
Nehmen wir an, der Brute-Force-Algorithmus findet eine Lsung und der obere nicht, dann wrde das bedeuten, dass der Algorithmus wegen der oberen Abbruchbedingung eine Zustand erreicht, in dem zwar noch Gegenstnde brig geblieben sind, diese aber nicht gekauft werden knnen, weil Gesamtpreis + Budget nicht ausreicht. D.h. es wurde bisher die alte Liste an Gegenstnden erworben und fr gnstigere reicht das Geld nicht mehr. Sei X der Preis des gnstigsten Gegenstandes, der nicht gekauft werden kann. Dann msste X > Budget sein, da aber mit dem teursten Gegenstand beim Einkaufen angefangen wird, also keine Gegenstand gnstiger als X erworben worden sein knnte, muss X auch der Preis des gnstigsten Elementes sein. Da aber X > Budget wre, und alle anderen Gegenstnde teuerer sind, kann auch der Brute-Force-Algorithmus keine Lsung gefunden haben, da ja von Anfang an kein einziger Gegenstand erworben worden sein htte knnnen.

Zumindest findet dieser Algorithmus also immer eine Lsung, wenn es sie gibt.
Mir ist leider kein Beweis eingefallen, mit dem gezeigt werden knnte, das der Algorithmus optimale Lsungen liefert und ich bin mir dessen auch nicht sicher. Denoch scheint er ein guter Kompromiss zwischen Leistung und Ergebnis zu sein.

2. Programm-Dokumentation
=========================

Das Programm verwendet STL und templates um die Quellcode-Gre klein zu halten und es funktioniert genau so wie in der Lsungsidee beschrieben. Die Funktion MultiSetWithoutMultiSet ist eine Hilfsfunktion, die einfach A \ B in STL-Code beschreibt.
FindOptimalSubMultiSet beinhaltet den oben beschriebenen Algorithmus und liefert den Betrag des nicht-verwendeten Restgeldes zurck.
In main behelfe ich mir eines Trickes um den neuen Gesamtwert der Gegenstnde zu bestimmen:
Da ich den alten Gesamtwert + Budget kenne, ist der neue Gesamtwert = alter Gesamtwert + Budget - Restgeld.

Das Progamm entnimmt dem ersten Befehlszeilenparameter den Dateinamen des Datensatzes und liest sie den Bespielen im Internet zufolge aus:
1. Zeile Budget
Folgende Zeilen Preise der Gegenstnde

3. Programm-Ablaufprotokoll:
============================

[...]>"Aufgabe 1.exe" beispiel0.txt
1. Verkauft: nichts Gekauft: 790 Gesamtwert: 790 Verloren: 210
2. Verkauft: 790 Gekauft: 340 1320 Gesamtwert: 1660 Verloren: 130
3. Verkauft: 1320 Gekauft: 2100 Gesamtwert: 2440 Verloren: 220
4. Verkauft: 340 Gekauft: 1320 Gesamtwert: 3420 Verloren: 20
5. Verkauft: nichts Gekauft: 790 Gesamtwert: 4210 Verloren: 210
6. Verkauft: 790 1320 2100 Gekauft: 5200 Gesamtwert: 5200 Verloren: 10
7. Verkauft: nichts Gekauft: 790 Gesamtwert: 5990 Verloren: 210
8. Verkauft: 790 Gekauft: 340 1320 Gesamtwert: 6860 Verloren: 130
9. Verkauft: 1320 Gekauft: 2100 Gesamtwert: 7640 Verloren: 220
10. Verkauft: 340 Gekauft: 1320 Gesamtwert: 8620 Verloren: 20
11. Verkauft: nichts Gekauft: 790 Gesamtwert: 9410 Verloren: 210
12. Verkauft: nichts Gekauft: 670 Gesamtwert: 10080 Verloren: 330
13. Verkauft: nichts Gekauft: 340 Gesamtwert: 10420 Verloren: 660

[...]>"Aufgabe 1.exe" beispiel1.txt
1. Verkauft: nichts Gekauft: 1 Gesamtwert: 1 Verloren: 0
2. Verkauft: 1 Gekauft: 2 Gesamtwert: 2 Verloren: 0
3. Verkauft: nichts Gekauft: 1 Gesamtwert: 3 Verloren: 0
.
.
.
131068. Verkauft: 1 2 Gekauft: 4 Gesamtwert: 131068 Verloren: 0
131069. Verkauft: nichts Gekauft: 1 Gesamtwert: 131069 Verloren: 0
131070. Verkauft: 1 Gekauft: 2 Gesamtwert: 131070 Verloren: 0
131071. Verkauft: nichts Gekauft: 1 Gesamtwert: 131071 Verloren: 0

[...]>"Aufgabe 1.exe" beispiel2.txt
1. Verkauft: nichts Gekauft: 8135 Gesamtwert: 8135 Verloren: 1865
2. Verkauft: 8135 Gekauft: 7567 10211 Gesamtwert: 17778 Verloren: 357
3. Verkauft: 7567 10211 Gekauft: 26530 Gesamtwert: 26530 Verloren: 1248
.
.
.
197. Verkauft: 8135 Gekauft: 7567 10211 Gesamtwert: 1688315 Verloren: 357
198. Verkauft: nichts Gekauft: 8135 Gesamtwert: 1696450 Verloren: 1865
199. Verkauft: nichts Gekauft: 7362 Gesamtwert: 1703812 Verloren: 2638

[...]>"Aufgabe 1.exe" beispiel3.txt
1. Verkauft: nichts Gekauft: 50 Gesamtwert: 50 Verloren: 0
2. Verkauft: 50 Gekauft: 100 Gesamtwert: 100 Verloren: 0
3. Verkauft: nichts Gekauft: 50 Gesamtwert: 150 Verloren: 0
4. Verkauft: 50 Gekauft: 100 Gesamtwert: 200 Verloren: 0
.
.
.
1023. Verkauft: 1 Gekauft: 3 6 6 6 6 6 6 6 6 Gesamtwert: 51150 Verloren: 0
1024. Verkauft: 3 Gekauft: 2 5 5 5 5 5 5 5 5 5 6 Gesamtwert: 51200 Verloren: 0
1025. Verkauft: 2 Gekauft: 3 4 4 4 4 4 4 5 5 5 5 5 Gesamtwert: 51250 Verloren: 0
1026. Verkauft: nichts Gekauft: 1 1 1 1 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 3 4 4 Gesamtwert: 51295 Verloren: 5

[...]>"Aufgabe 1.exe" beispiel4.txt
Es gibt keine Lsung fr diesen Datensatz!
